#include <stdio.h>
#include <stdlib.h>

typedef int DATA;
//#define NULL 0;
#define LEN sizeof(struct node)

struct node
{
    DATA data;

    struct node *left;
    struct node *right;
};

struct node *creatnewNode(int data)
{
    struct node *newNode = (struct node *)malloc(LEN);
    if(newNode == NULL) return NULL;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

//插入节点
struct node *insertNode(struct node *root,int data)
{
    struct node *newNode = creatnewNode(data);
    //若树为空，直接
    if(root == NULL) return newNode;

    if(newNode->data < root->data)
        root->left = insertNode(root->left,newNode->data);
    else if(newNode->data > root->data)
        root->right = insertNode(root->right,newNode->data);
    else
    {
        printf("%d已经存在\n",newNode->data);
        free(newNode);
    }
    
    return root;
}

//删除
struct node *bstRemove(struct node *root,int data)
{
    if(root == NULL)
        return NULL;

    if(data < root->data)
        root->left = bstRemove(root->left,data);
    else if(data > root->data)
        root->right = bstRemove(root->right,data);
    
    //要删除的就是当前的根节点
    else
    {
        //当前有左子树
        if(root->left != NULL)
        {
            //找到左子树中最大的节点
            struct node *p;
            for(p = root->left;p->right!=NULL;p = p->right);

            //替换
            root->data = p->data;

            //将左子树中多以节点删除
            root->left = bstRemove(root->left,p->data);
        }

        //没有左子树但是有右子树
        else if(root->right != NULL)
        {
            //找到右子树中最小的节点
            struct node *p;
            for(p = root->right;p->left!=NULL;p = p->left);

            //替换
            root->data = p->data;

            //将右子树中多以节点删除
            root->right = bstRemove(root->right,p->data);
        }

        //当前没有任子树
        else
        {
            free(root);
            return NULL;
        }
    }
    return root;
}


//前序遍历：根-左子树-右子树
void pre_order(struct node *root)
{
    if(root == NULL)
        return;

    printf("%d\t",root->data);
    pre_order(root->left);
    pre_order(root->right);
}

//中序遍历：左子树-根-右子树
void mid_order(struct node *root)
{
    if(root == NULL)
        return;

    mid_order(root->left);
    printf("%d\t",root->data);
    mid_order(root->right);
}

//后序遍历：左子树-右子树-根
void post_order(struct node *root)
{
    if(root == NULL)
        return;

    post_order(root->left);
    post_order(root->right);
    printf("%d\t",root->data);
}


int main(int argc, char const *argv[])
{
    //定义一个根节点
    struct node *root = NULL;

    root = insertNode(root,5);
    root = insertNode(root,4);
    root = insertNode(root,6);
    root = insertNode(root,1);
    root = insertNode(root,7);
    root = insertNode(root,9);
    root = insertNode(root,3);
    root = insertNode(root,2);
    root = insertNode(root,8);

    bstRemove(root,5);

    pre_order(root);
    printf("\n");
    mid_order(root);
    printf("\n");
    post_order(root);
    printf("\n");

    return 0;
}
